package sortTests;

import java.util.List;

public class HeapSort implements ISorter {
	
	@Override
	public void sort(List<Integer> array) {
		if (array.size() <= 1) return;
		
		buildHeap(array);
		
		for (int i = 1; i < array.size(); i++) {
			int last = array.size()-i;
			int t = array.get(0);
			
			array.set(0, array.get(last));
			array.set(last, t);
			heapify(array.subList(0, last), 0);
		}
	}
	
	private static void buildHeap(List<Integer> array) {
		for (int i = array.size()/2; i >=0; i--) {
			heapify(array, i);
		}
	}
	
	private static void heapify(List<Integer> array, int index) {
		if (index > array.size()) return;
		int left = 2*index+1;
		int right = 2*index+2;
		int largest = index;
		if (left < array.size())
			if (array.get(left) > array.get(largest))
				largest = left;
		if (right < array.size())
			if (array.get(right) > array.get(largest))
				largest = right;
		if (largest != index) {
			int t = array.get(index);
			array.set(index, array.get(largest));
			array.set(largest, t);
			heapify(array, largest);
		}
	}
}
